import java.util.*;
public class OrionsKey{
    public static void main(String[] args){
        int[] arr = new int[10001];
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i < 10001;i++){
            arr[i] = arr[i - 1] + arr[i - 2];
             arr[i] =  arr[i] % 10000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuffer sb = new StringBuffer();
            int n = sc.nextInt();
            for(int i = 0;i < n;i++){
                int x = sc.nextInt();
                sb.append(String.format("%04d",arr[x]));
            }
            System.out.println(sb);
        }
        
    }    
}
